package cn.bouncyslime.algorithms.sort.swapSort.quickSort;

import java.util.Random;

// 随机获取枢轴的位置
public class SortQuick4 {
	//进行第一次排序，之后找到轴的位置后对得到的左小右大的数列分别再进行排序
	public void quickSort(int[] array, int low, int high) {
		int cenPos = 0;
		if(low<high) {
			cenPos = parting(array, low, high);
			quickSort(array,low,cenPos-1);
			quickSort(array,cenPos+1,high);
		}
	}
	
	//进行一次排序，改变中轴的位置，此方法运行完数组中轴左边的数都比轴数小，右边的都比它大
	public int parting(int[] array, int low, int high) {
		//初始轴的位置进行随机选择（中轴的位置有影响，采用不同的中轴位置，对算法会有改进）
		Random r = new Random();
		int cenPos = r.nextInt(high-low)+low;
		System.out.println("排序中轴的初始位置："+cenPos);
		int cenValue = array[cenPos];
		//该循环进行此方法的主要操作，左小右大的划分
		while(low<high) {
			while(low < high && array[high]>=cenValue && high>cenPos) {
				high--;
			}
			if(low<high) {
				array[cenPos] = array[high];
				cenPos = high;
			}
			while(low < high && array[low]<=cenValue && low<cenPos) {
				low++;
			}
			if(low<high) {
				array[cenPos] = array[low];
				cenPos = low;
			}
			printArray(array);
		}
		array[cenPos] = cenValue;
		
		printArray(array);
		System.out.println("以上排序中轴的最终位置 "+cenPos);
		//一遍左小右大的排序完成之后，返回最终轴的位置，为后面的操作创造条件
		return cenPos;
	}
	
	//该方法输出传入的数列
	public void printArray(int[] array) {
		for(int i=0; i<array.length; i++) {
			System.out.printf("%d ",array[i]);
		}
		System.out.println();
	}
	
	
	public static void main(String[] args) {
		int[] array = {11,13,2,34,55,9,44,122,32,2,9};
		SortQuick4 sq = new SortQuick4();
		
		sq.printArray(array);
		System.out.println("初始");
		sq.quickSort(array, 0, array.length-1);
		
		sq.printArray(array);
	}
}
